void swap(int *i, int *j) 
{
    *i = *i ^ *j;
    *j = *i ^ *j;
    *i = *i ^ *j;

    return;
}

/*
* bubble
*/
void bubble_sort (int arr[], int length) 
{
    if (arr == NULL || length < 2) return;  // 小于一个元素不排序

    int flag = 0;   //当flag=0 提前结束排序，说明数组本来就是有序的
    //end的意思就是把冒泡出来的值放到这个地方，每次都放到end
    for (int end = length -1 ; end > 0; end--, flag = 0) {
        for (int i = 0; i < end; i++) {
            if (arr[i] > arr[i+1]) {
                swap(&arr[i], &arr[i+1]);
                flag = 1;
            }
        }
        if (flag == 0) break;
    }
    return;
}

/*
* selection
*/
void selection_sort (int arr[], int length) 
{
    if (arr == NULL || length < 2) return;  // 小于一个元素不排序
    int min_index = 0;
    
    for (int i = 0 ; i < length - 1;  i++) {
        min_index = i; //提前预设一个最小下标
        for (int j = i + 1; j < length; j++) {
            min_index = arr[min_index] > arr[j] ? j : min_index; 
        }
        if ( min_index != i) swap(&arr[min_index], &arr[i]);  //使用异或来交换数据，不能交换两个相同的值，他会把这个值变为0
    }
    return;
}

/*
* insert
*/
void insert_sort (int arr[], int length) 
{
    if (arr == NULL || length < 2) return;  // 小于一个元素不排序

    for (int i = 1 ; i < length;  i++) {
        for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) { //从后往前插入, 一旦数组是有序的（arr[j] >= arr[j-1]），for循环可以提前结束,降低时间复杂度
                swap(&arr[j], &arr[j - 1]);
        }
    }
    return;
}

/*
* insert1
*/
void insert_sort (int arr[], int length) 
{
    if (arr == NULL || length < 2) return;  // 小于一个元素不排序

    for (int i = 1 ; i < length;  i++) {  //待排序区间
        int value = a[i]
        for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) { //从后往前插入, 一旦数组是有序的（arr[j] >= arr[j-1]），for循环可以提前结束,降低时间复杂度
//                swap(&arr[j], &arr[j - 1]);
                a[j] = a[j - 1];  //只移动不交换
        }
        a[j] = value;
    }
    return;
}
/*
* 归并排序
*/
//divide_conquer_sort

void conquer(int arr[], int left, int mid, int right)
{
    int *aux = (int*)malloc((right - left + 1)*sizeof(int));
    if (!aux) {
         perror("malloc");
         printf("conquer\n");
         exit(-1);
     }
    memset(aux, 0, (right - left + 1)*sizeof(int));
    int pl = left;
    int pr = mid + 1; // 容易出错
    int i = 0;
    while (pl <= mid && pr <= right) {
        aux[i++] = arr[pl] < arr[pr] ? arr[pl++] : arr[pr++];
    }
    while (pl <= mid) {
        aux[i++] = arr[pl++];
    }
    while (pr <= right) {
        aux[i++] = arr[pr++];
    }

    for (i = 0; i < (right - left + 1); i++) {
        arr[left + i] = aux[i]; // 容易出错
    }
    if (aux) free(aux);
    aux = NULL
}

void d_c_sort(int arr[], int left, int right)
{
    //  if (left >= right) return;
    if (left == right) return; 
//  mid = (left + right)/2 有可能导致中间结果溢出
    int mid = left + ((right - left) >> 1);

    d_c_sort(arr, left, mid);
    d_c_sort(arr, mid + 1, right);
    conquer(arr, left, mid, right);
}

void divide_conquer_sort(int arr[], int length)
{
    if (arr == NULL || length < 2) return;

    d_c_sort(arr, 0, length - 1);
}


// swap two intergers pointed by a and b
void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

// partition the array and return the index of the pivot element
void partition(int *nums, int left, int right, int *q)
{
	int more = nums[right]; // pivot
	int less = left - 1;
	
	while (left < more) { // loop until left and more meet each other
        if (nums[left] < nums[right]) { // if the element is less pivot, move it to the left part of the array
            swap(&nums[++less], &nums[left++]);
        } else if (nums[left] > nums[right]) { // if the element is more than pivot, move it to the right part of the array
            swap(&nums[left], &nums[--more]);
        } else { // if the element is equal to pivot, just move to the next element
            left++;
        }
    }
    swap(&nums[more], &nums[right]); // put the pivot to the middle of the array
    q[0] = ++less;
    q[1] = more;
    return;
}

void q_sort_internal(int *nums, int left, int right) // quick sort algorithm with recursion and stack
{
    if (left < right) {
        srand((unsigned)time(NULL)); // initialize random seed
        int rnd = rand() % (right - left + 1) + left; // generate a random number between left and right index of the array
        swap(&nums[rnd], &nums[right]); // swap the pivot element with the last element of the array
        int q[2] = {0}; // store the index of the pivot element after partitioning the array
        partition(nums, left, right, q); // partition the array and get the index of the pivot element after partitioning the array
        q_sort_internal(nums, left, q[0] - 1); // sort the left part of the array recursively  
        q_sort_internal(nums, q[1] + 1, right); // sort the right part of the array recursively
    }
}
void q_sort(int *nums, int len) // quick sort algorithm with recursion and stack
{
    if (nums == NULL || len <= 1) return; // if the array is empty or contains only one element, return directly
    q_sort_internal(nums, 0, len - 1); // sort the array recursively
}


/*
*堆排
*/

//从上
void heapify(int *nums, int i, int heap_size)
{
    int left = i*2 + 1;
    while (left < heap_size) {
        int largest = (left + 1) < heap_size && nums[left + 1 ] > nums[left]?left + 1:left;
        largest = nums[i] > nums[largest]?i:largest;
        if (largest == i) break;
        swap(&nums[i], &nums[largest]);
        i = largest;  // 这步不能省，下一步要用
        left = largest*2 + 1;
    }
}

//从下, 大顶堆
void heap_insert(int* nums, int i)
{
    while (nums[i] > nums[(i-1)/2]) { // (-1) / 2 == 0
        swap(&nums[i], &nums[(i-1)/2]);
        i = (i-1)/2;
    }
}

void heap_sort(int *nums, int length)
{
    if (!nums || length <2) return;

    for (int i = 0; i < length; i++) {
        heap_insert(nums, i);
    }

    swap(&nums[0], &nums[--length]); // 生成最大元素
    while (length > 0) {
        heapify(nums, 0, length);
        swap(&nums[0], &nums[--length]);
    }
    return;
}



//剑指 Offer 51. 数组中的逆序对

int conquer(int* nums, int left, int mid, int right, int* aux)
{
// 不能频繁的申请释放内存，要一次性搞定
/*    int *aux = (int*)malloc((right - left + 1)*sizeof(int));  
    if (!aux) {
         perror("malloc");
         printf("conquer\n");
         exit(-1);
     }
*/
    int pl = left;
    int pr = mid + 1;
    int res = 0, i = 0;
    while (pl <= mid && pr <= right) {
        res += (nums[pl] > nums[pr]) ? (right - pr + 1):0;
        aux[i++] = nums[pl] > nums[pr] ? nums[pl++] : nums[pr++];
    }
    while (pl <= mid) {
        aux[i++] = nums[pl++];
    }
    while (pr <= right) aux[i++] = nums[pr++];

    for (i = 0; i < (right -left + 1); i++) {
        nums[left+i] = aux[i];
    }
//   if(aux) free(aux);
//   aux = NULL;
    return res;
}

int d_c_sort(int* nums, int left, int right, int* aux)
{
    if (left == right) return 0;
    int mid = left + ((right - left) >> 1);
    return d_c_sort(nums, left, mid, aux) + d_c_sort(nums, mid + 1, right, aux)\
        +conquer(nums, left, mid, right, aux);
}

int reversePairs(int* nums, int numsSize){
    if (nums == NULL || numsSize < 2 ) return 0;
    int *aux = (int*)malloc(numsSize*sizeof(int));
    if (!aux) {
         perror("malloc");
         printf("reversePairs\n");
         exit(-1);
     }
    int res = d_c_sort(nums, 0, numsSize - 1, aux);
    if (aux) free(aux);
    aux = NULL;
    return res
}